This invention relates to convolution function generators and to their utilization in digital filters.
The values of a series of samples y.sub.n of an output signal provided by a filter discretely defined by its set of coefficients h.sub.n and fed by the series of samples x.sub.n of a signal to be filtered are determined by the following convolution relation: ##EQU2## WHICH SHOWS THE NEED FOR CONVOLUTION FUNCTION GENERATORS.
The most obvious manner for building such a device consists in using N+1 multipliers and N adders thus directly performing the operations symbolized by expression (1). However, it is not the least expensive manner, nor the fastest. More especially since the quality of filtering is directly related to N: the greater N is, the better the filtering.
Under such constraints, it is desirable to build filtering devices which require less computing power than this obvious type but give an equivalent filtering quality. For this purpose, consideration was given to the use of the properties of certain mathematical transforms among which, one may mention the Fourier transform or the Mersenne transform described by Charles M. Rader in an article entitled, "Discrete Convolution via Mersenne Transforms," published in the "IEEE Transactions on Computers," Vol. C. 21, No. 12, December 1972, pages 1269-1273. Said Mersenne transform and its inverse show several desirable properties. First of all, term-to-term products in the transform domain correspond to convolutions in the object domain. Otherwise stated, if X.sub.k and H.sub.k, respectively, are the transforms of the x.sub.n and h.sub.n terms, and if the term-to-term products X.sub.k . H.sub.k = Y.sub.k are generated, the application of the inverse Mersenne transform to the Y.sub.k 's provides the desired y.sub.n 's. Thus, the convolution theorem applies to the Mersenne transform. In addition, the transpositions from the object domain to the Mersenne one, and conversely, require only additions and shifts, which is one reason for the interest taken in a convolution function generator based on the properties of the Mersenne transform.
But one of the major disadvantages of such a device rests in the fact that it should be able to process words whose size depends on the number of samples x.sub.n and h.sub.n, to which the transforms are applied, thus practically limiting the application of this solution to short convolutions.
French patent application No. 75 12557, filed on Apr. 16, 1975 by the assignee of this invention and corresponding to this applicant's U.S. patent application Ser. No. 670,325, filed Mar. 25, 1976 describes a convolution function generator using a variant of the Mersenne transform, in which the required computing power is still lower than that of a normal Mersenne convolutor. This allows the implementation of convolutors operating on medium length series of terms.